home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / zoo21src.zoo / wildmat.c < prev    next >
C/C++ Source or Header  |  1991-07-24  |  13KB  |  508 lines
  1. /*  $Revision: 1.7 $
  2. **
  3. **  Do shell-style pattern matching for ?, \, [], and * characters.
  4. **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
  5. **  could cause a segmentation violation.  It is 8bit clean.
  6. **
  7. **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
  8. **  Rich $alz is now <rsalz@bbn.com>.
  9. **  April, 1991:  Replaced mutually-recursive calls with in-line code
  10. **  for the star character.
  11. **
  12. **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
  13. **  This can greatly speed up failing wildcard patterns.  For example:
  14. **    pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
  15. **    text 1:     -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
  16. **    text 2:     -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
  17. **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
  18. **  the ABORT, then it takes 22310 calls to fail.  Ugh.  The following
  19. **  explanation is from Lars:
  20. **  The precondition that must be fulfilled is that DoMatch will consume
  21. **  at least one character in text.  This is true if *p is neither '*' nor
  22. **  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
  23. **  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
  24. **  FALSE, each star-loop has to run to the end of the text; with ABORT
  25. **  only the last one does.
  26. **
  27. **  Once the control of one instance of DoMatch enters the star-loop, that
  28. **  instance will return either TRUE or ABORT, and any calling instance
  29. **  will therefore return immediately after (without calling recursively
  30. **  again).  In effect, only one star-loop is ever active.  It would be
  31. **  possible to modify the code to maintain this context explicitly,
  32. **  eliminating all recursive calls at the cost of some complication and
  33. **  loss of clarity (and the ABORT stuff seems to be unclear enough by
  34. **  itself).  I think it would be unwise to try to get this into a
  35. **  released version unless you have a good test data base to try it out
  36. **  on.
  37. */
  38.  
  39. #define TRUE            1
  40. #define FALSE            0
  41. #define ABORT            -1
  42.  
  43.  
  44.     /* What character marks an inverted character class? */
  45. #define NEGATE_CLASS        '^'
  46.     /* Is "*" a common pattern? */
  47. #define OPTIMIZE_JUST_STAR
  48.     /* Do tar(1) matching rules, which ignore a trailing slash? */
  49. #undef MATCH_TAR_PATTERN
  50.  
  51.  
  52. /*
  53. **  Match text and p, return TRUE, FALSE, or ABORT.
  54. */
  55. static int
  56. DoMatch(text, p)
  57.     char    *text;
  58.     char    *p;
  59. {
  60.     int    last;
  61.     int    matched;
  62.     int    reverse;
  63.  
  64.     for ( ; *p; text++, p++) {
  65.     if (*text == '\0' && *p != '*')
  66.         return ABORT;
  67.     switch (*p) {
  68.     case '\\':
  69.         /* Literal match with following character. */
  70.         p++;
  71.         /* FALLTHROUGH */
  72.     default:
  73.         if (*text != *p)
  74.         return FALSE;
  75.         continue;
  76.     case '?':
  77.         /* Match anything. */
  78.         continue;
  79.     case '*':
  80.         while (*++p == '*')
  81.         /* Consecutive stars act just like one. */
  82.         continue;
  83.         if (*p == '\0')
  84.         /* Trailing star matches everything. */
  85.         return TRUE;
  86.         while (*text)
  87.         if ((matched = DoMatch(text++, p)) != FALSE)
  88.             return matched;
  89.         return ABORT;
  90.     case '[':
  91.         reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
  92.         if (reverse)
  93.         /* Inverted character class. */
  94.         p++;
  95.         for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
  96.         /* This next line requires a good C compiler. */
  97.         if (*p == '-' ? *text <= *++p && *text >= last : *text == *p)
  98.             matched = TRUE;
  99.         if (matched == reverse)
  100.         return FALSE;
  101.         continue;
  102.     }
  103.     }
  104.  
  105. #ifdef    MATCH_TAR_PATTERN
  106.     if (*text == '/')
  107.     return TRUE;
  108. #endif    /* MATCH_TAR_ATTERN */
  109.     return *text == '\0';
  110. }
  111.  
  112.  
  113. /*
  114. **  User-level routine.  Returns TRUE or FALSE.
  115. */
  116. int
  117. wildmat(text, p)
  118.     char    *text;
  119.     char    *p;
  120. {
  121. #ifdef    OPTIMIZE_JUST_STAR
  122.     if (p[0] == '*' && p[1] == '\0')
  123.     return TRUE;
  124. #endif    /* OPTIMIZE_JUST_STAR */
  125.     return DoMatch(text, p) == TRUE;
  126. }
  127.  
  128. #include <stdio.h>
  129. #include <sys/types.h>
  130. #include <dirent.h>
  131. #include <sys/stat.h>
  132. #if __STDC__
  133. #ifdef unix
  134. #define _SIZE_T    /* unix defines size_t in sys/types.h */
  135. #endif
  136. #ifndef _COMPILER_H
  137. #  include <compiler.h>
  138. #endif
  139. #include <stddef.h>
  140. #include <stdlib.h>
  141. #else
  142. extern char *malloc(), *realloc();
  143. extern char *rindex(),  *strdup();
  144. #define __PROTO(x) ()
  145. #endif
  146. #include <string.h>
  147.  
  148. #define MAX_DIR    32    /* max depth of dir recursion */
  149. static struct {
  150.     char *dir, *patt;
  151. } dir_stack[MAX_DIR];
  152. static int stack_p;
  153. static char **matches;
  154. static int nmatches;
  155.  
  156. static void *ck_memalloc __PROTO((void *));
  157. #define ck_strdup(p) ck_memalloc(strdup(p))
  158. #define ck_malloc(s) ck_memalloc(malloc(s))
  159. #define ck_realloc(p, s) ck_memalloc(realloc(p, s))
  160.  
  161.  
  162. #define DEBUGX(x) 
  163.  
  164. /*
  165.  * return true if patt contains a wildcard char
  166.  */
  167. int contains_wild(patt)
  168. char *patt;
  169. {
  170.     char c;
  171.     char *p;
  172.  
  173.     /* only check for wilds in the basename part of the pathname only */
  174.     if((p = rindex(patt, '/')) == NULL)
  175.     p = rindex(patt, '\\');
  176.     if(!p)
  177.     p = patt;
  178.  
  179.     while((c = *p++))
  180.     if((c == '*') || (c == '?') || (c == '['))
  181.         return 1;
  182.     return 0;
  183. }
  184.  
  185. #ifndef ZOO
  186. void free_all()
  187. {
  188.     char **p;
  189.  
  190.     if(!matches)
  191.     return;
  192.  
  193.     for(p = matches; *p; p++)
  194.     free(*p);
  195.     free(matches);
  196.     matches = NULL;
  197. }
  198. #endif
  199.  
  200. static void push(dir, patt)
  201. char *dir;
  202. char *patt;
  203. {
  204.     if(stack_p < (MAX_DIR - 2))
  205.     stack_p++;
  206.     else
  207.     {
  208.     fprintf(stderr,"directory stack overflow\n");
  209.     exit(99);
  210.     }
  211.     dir_stack[stack_p].dir = dir;
  212.     dir_stack[stack_p].patt = patt;
  213. }
  214.  
  215. /*
  216.  * glob patt
  217.  * if decend_dir is true, recursively decend any directories encountered.
  218.  * returns pointer to all matches encountered.
  219.  * if the initial patt is a directory, and decend_dir is true, it is
  220.  * equivalent to specifying the pattern "patt\*"
  221.  *
  222.  * Restrictions:
  223.  *  - handles wildcards only in the base part of a pathname
  224.  *    ie: will not handle \foo\*\bar\ (wildcard in the middle of pathname)
  225.  *
  226.  *  - max dir recursion is MAX_DIR
  227.  *
  228.  *  - on certain failures it will just skip potential matches as if they
  229.  *    were not present.
  230.  *
  231.  *  ++jrb    bammi@cadence.com
  232.  */
  233. static char **do_match __PROTO((int decend_dir));
  234.  
  235. char **glob(patt, decend_dir)
  236. char *patt;
  237. int decend_dir;
  238. {
  239.     char *dir, *basepatt, *p;
  240.     struct stat s;
  241.  
  242.     DEBUGX((fprintf(stderr,"glob(%s, %d)\n", patt, decend_dir)));
  243.     matches = NULL;
  244.     nmatches = 0;
  245.     stack_p = -1;
  246.  
  247.     /* first check for wildcards */
  248.     if(contains_wild(patt))
  249.     {
  250.     /* break it up into dir and base patt, do_matches and return */
  251.     p = ck_strdup(patt);
  252.     if((basepatt = rindex(p, '/')) == NULL)
  253.         basepatt = rindex(p, '\\');
  254.         if(basepatt)
  255.         {
  256.         dir = p;
  257.         *basepatt++ = '\0';
  258.         basepatt = ck_strdup(basepatt);
  259.         }
  260.         else
  261.         {
  262.         dir = ck_strdup(".");
  263.         basepatt = p;
  264.         }
  265.  
  266.         if(strcmp(basepatt, "*.*") == 0)
  267.         {
  268.             /* the desktop, and other braindead shells strike again */
  269.             basepatt[1] = '\0';
  270.         }
  271.     push(dir, basepatt);
  272.     DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
  273.     return do_match(decend_dir);
  274.     }
  275.  
  276.     /* if no wilds, check for dir */
  277.     if(decend_dir && (!stat(patt, &s)))
  278.     {
  279.     if((s.st_mode & S_IFMT) == S_IFDIR)
  280.     {   /* is a dir */
  281.         size_t len = strlen(patt);
  282.         
  283.         dir = ck_strdup(patt);
  284.         --len;
  285.         if(len && ((dir[len] == '/') 
  286. #ifdef atarist
  287.            || (dir[len] == '\\')
  288. #endif
  289.          ))
  290.         dir[len] = '\0';
  291.         basepatt = ck_strdup("*");
  292.         push(dir, basepatt);
  293.         DEBUGX((fprintf(stderr, "calling %s, %s\n", dir, basepatt)));
  294.         return do_match(decend_dir);
  295.         }
  296.     }
  297.     return NULL;
  298. }
  299.  
  300. static char **do_match(decend_dir)
  301. int decend_dir;
  302. {
  303.     DIR *dirp;
  304.     struct dirent *d;
  305.     struct stat s;
  306.     char *dir, *basepatt;
  307.  
  308.     while(stack_p >= 0)
  309.     {
  310.     dir = ck_strdup(dir_stack[stack_p].dir); 
  311.     free(dir_stack[stack_p].dir);
  312.         basepatt = ck_strdup(dir_stack[stack_p].patt);
  313.     free(dir_stack[stack_p--].patt);
  314.     
  315.         DEBUGX((fprintf(stderr,"dir %s patt %s stack %d\n